﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _01背包
{
    public class Solution
    {
        public int[] weights;
        public int[] values;
        public int W;

        public Solution(int[] weights, int[] values, int W)
        {
            this.weights = weights;
            this.values = values;
            this.W = W;
        }

        public int Solve()
        {
            int n = weights.Length;

            int[,] Vs = new int[n, W + 1];
            bool[,] flag = new bool[n, W + 1];

            for (int j = 0; j <= W; j++)
            {
                if (j + weights[0] <= W)
                {
                    Vs[0, j] = values[0];
                    flag[0, j] = true;
                }
            }

            for (int i = 1; i < n; i++)
            {
                for (int j = 0; j <= W; j++)
                {
                    Vs[i, j] = Vs[i - 1, j];
                    if (j + weights[i] <= W)
                    {
                        int may = Vs[i - 1, j + weights[i]] + values[i];
                        if (may > Vs[i, j])
                        {
                            Vs[i, j] = may;
                            flag[i, j] = true;
                        }
                    }
                }
            }

            int r = 0;
            int index = -1;
            for (int j = 0; j <= W; j++)
            {
                if(Vs[n - 1, j] > r)
                {
                    r = Vs[n - 1, j];
                    index = j;
                }
            }

            List<bool> buys = new();
            for(int i = n - 1; i >= 0; i--)
            {
                if (flag[i, index])
                {
                    buys.Add( true);
                    index += weights[i];
                }
                else
                {
                    buys.Add(false);
                }
            }

            Console.WriteLine("购买方案");
            int w = 0;
            for(int i = buys.Count-1; i >= 0; i--)
            {
                Console.Write(buys[i] + " ");
                if (buys[i])
                {
                    w += weights[weights.Length - 1 - i];
                }
            }
            Console.WriteLine();
            Console.WriteLine("总重:" + w);
            Console.WriteLine();

            return r;
        }
    }
}
